﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;

namespace Redis读写分离.Filter
{
    /// <summary>
    /// 布谷鸟过滤器实现：支持插入、查找、删除，效率高、空间使用率高。
    /// </summary>
    public class CuckooFilter
    {
        private readonly Bucket[] buckets;  // 存储所有桶，每个桶存 fingerprint 列表
        private readonly int bucketSize;    // 每个桶可存放的 fingerprint 数量
        private readonly int maxKicks;      // 最大尝试次数（踢出替换）防止死循环
        private readonly int capacity;      // 总桶数（决定索引范围）
        private readonly Random rand;       // 随机数生成器，用于踢出随机 fingerprint

        // 初始化桶数组和参数
        public CuckooFilter(int capacity, int bucketSize = 4, int maxKicks = 500)
        {
            this.capacity = capacity;
            this.bucketSize = bucketSize;
            this.maxKicks = maxKicks;
            this.rand = new Random();

            // 初始化桶，每个桶能装 bucketSize 个 fingerprint
            buckets = new Bucket[capacity];
            for (int i = 0; i < capacity; i++)
                buckets[i] = new Bucket(bucketSize);
        }

        // 插入元素，返回是否成功
        public bool Add(string item)
        {
            ushort fp = Fingerprint(item);   // 生成 fingerprint（指纹）
            int i1 = IndexHash(item);        // 第一个桶索引
            int i2 = AltIndex(i1, fp);       // 第二个桶索引（i1 异或指纹哈希）

            // 尝试插入任一桶
            if (buckets[i1].Insert(fp) || buckets[i2].Insert(fp))
                return true;

            // 两个桶都满了，随机选择一个桶进行踢出策略
            int i = rand.Next(0, 2) == 0 ? i1 : i2;
            for (int n = 0; n < maxKicks; n++)
            {
                // 将新 fingerprint 插入，同时踢出旧的（随机位置），再尝试插入旧的到另一个候选桶
                fp = buckets[i].SwapRandom(fp, rand);
                i = AltIndex(i, fp);
                if (buckets[i].Insert(fp))
                    return true;
            }

            // 插入失败（超过最大尝试次数）
            return false;
        }

        // 判断元素是否存在
        public bool Contains(string item)
        {
            ushort fp = Fingerprint(item);
            int i1 = IndexHash(item);
            int i2 = AltIndex(i1, fp);

            // 在两个候选桶中查找 fingerprint
            return buckets[i1].Contains(fp) || buckets[i2].Contains(fp);
        }

        // 删除元素
        public bool Delete(string item)
        {
            ushort fp = Fingerprint(item);
            int i1 = IndexHash(item);
            int i2 = AltIndex(i1, fp);

            // 从两个候选桶中尝试删除
            return buckets[i1].Delete(fp) || buckets[i2].Delete(fp);
        }

        // 生成 fingerprint（将哈希结果转为 16 位）
        private ushort Fingerprint(string item)
        {
            using (SHA256 sha = SHA256.Create())
            {
                byte[] hash = sha.ComputeHash(Encoding.UTF8.GetBytes(item));
                return BitConverter.ToUInt16(hash, 0); // 只取前 2 个字节作为 fingerprint
            }
        }

        // 计算第一个索引位置（桶编号）
        private int IndexHash(string item)
        {
            using (SHA256 sha = SHA256.Create())
            {
                byte[] hash = sha.ComputeHash(Encoding.UTF8.GetBytes(item));
                return BitConverter.ToInt32(hash, 0) & (capacity - 1); // 与 (容量-1) 做位运算保持在范围内
            }
        }

        // 计算备选索引（第二个桶位置）
        private int AltIndex(int index, ushort fingerprint)
        {
            int hash = fingerprint.GetHashCode();       // 计算 fingerprint 的哈希值
            return (index ^ hash) & (capacity - 1);     // 当前索引异或后哈希，确保仍在范围内
        }
    }

    // 桶类：用于保存多个 fingerprint 值（最多 capacity 个）
    public class Bucket
    {
        private readonly List<ushort> fingerprints; // 实际存储 fingerprint 的列表
        private readonly int capacity;              // 最大容量（通常是 4）

        //初始化容量
        public Bucket(int capacity)
        {
            this.capacity = capacity;
            fingerprints = new List<ushort>(capacity);
        }

        public bool Insert(ushort fingerprint)
        {
            if (fingerprints.Count < capacity)
            {
                fingerprints.Add(fingerprint);
                return true;
            }
            return false; // 桶满了
        }

        public bool Delete(ushort fingerprint)
        {
            return fingerprints.Remove(fingerprint);
        }

        public bool Contains(ushort fingerprint)
        {
            return fingerprints.Contains(fingerprint);
        }

        // 随机替换一个 fingerprint，并返回被替换的原值
        public ushort SwapRandom(ushort fingerprint, Random rand)
        {
            int index = rand.Next(fingerprints.Count); // 随机选择一个位置
            ushort victim = fingerprints[index];       // 被踢出的值
            fingerprints[index] = fingerprint;         // 用新的值替换它
            return victim;
        }
    }

}
